package com.gitee.ywj1352.算法.真实;

import com.gitee.ywj1352.算法.week02.TreeNode;

import java.util.HashMap;

public class



从前序与中序遍历序列构造二叉树 {

    HashMap<Integer, Integer> map;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        map = new HashMap<Integer, Integer>();

        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }

        return myBuild(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
    }

    public TreeNode myBuild(int[] preorder, int pL, int pR, int[] inorder, int iL, int iR) {
        if (pL > pR || iL > iR) {
            return null;
        }
        int val = preorder[pL];
        TreeNode node = new TreeNode(val);
        int pi = map.get(val);

        //画图找下标
        TreeNode left = myBuild(preorder, pL + 1, pi + pL - iL, inorder, iL, pi - 1);
        TreeNode right = myBuild(preorder, pi + pL - iL + 1, pR, inorder, pi + 1, iR);
        node.left = left;
        node.right = right;
        return node;
    }


}
